#ifndef GCD_H
#define GCD_H

#include <cassert>
#include "remainder.h"

template<typename T>
T subtractive_gcd_nonzero(T a, T b)
{
	assert(a > 0);
	assert(b > 0);
	while(true) {
		if (b < a)
			a = a - b;
		else if (a < b)
			b = b - a;
		else
			return a;
	}
}

template<typename T>
T subtractive_gcd(T a, T b)
{
	assert(a >= 0 && b >= 0 && a + b != 0);
	while(true) {
		if (b == 0) return a;
		while (b <= a) a = a - b;
		if (a == 0) return b;
		while (a <= b) b = b - a;
	}
}

template<typename T>
T fast_subtractive_gcd(T a, T b)
{
	while (true) {
		if (b == 0) return a;
		a = remainder_nonnegative(a, b);
		if (a == 0) return b;
		b = remainder_nonnegative(b, a);
	}
}

#endif